\section{Read Write Lock}

\subsection{Resumen}
\indent Se nos pide implementar un \textit{Read Write Lock} 
para $threads$ utilizando las primitivas de sincronización de la librería $pthread$. 
Nos basamos en el algoritmo presentado por Allen B. Downey en 
su libro \textit{The Little Book of Semaphores} y propusimos una semántica 
para facilitar la comprensión del problema y dar un leguanje común para hablar de él. 
Se nos pide además que nuestra implementación esté libre de inanición. 
Decidimos priorizar el diseño y la claridad del código para minimizar 
los errores y facilitar su lectura. Esta decisión nos llevó usar una 
implementación propia de semáforos y a encapsular el código en algunas clases.
Finalmente, diseñamos y ejecutamos un test de estrés 
para poner a prueba nuestra implementación.

\subsection{Algoritmo}

\indent El problema de los lectores y escritores es un problema clásico de sincronización 
de procesos. Existen muchas formas de plantearlo, nosotros proponemos una en particular:

\begin{itemize}

\item Hay lectores, escritores y una sala de lectura con un pizarrón.
\item Cualquier cantidad de lectores pueden estar adentro de la sala de lectura leyendo el pizarrón.
\item Los escritores tienen acceso exclusivo a la sala de lectura para usar el pizarrón.

\end{itemize}
 
\indent En otras palabras, un escritor no puede entrar a la sala de lectura 
mientras cualquier otro (escritor o lector) se encuentre ahí y si hay un escritor adentro 
de la sala de lectura, ningún otro (escritor o lector) puede entrar.

\indent Consideremos una semántica para semáforos en la que 
hacer $wait$ sobre una condición signifique 
\textit{esperar a que dicha condición sea verdadera} y 
hacer $signal$ signifique \textit{afirmar que es verdadera}. 
El seudocódigo de una solución posible para este problema sería el siguiente:

\begin{verbatim}
# Variables comunes
int lectores = 0
mutex = Semaphore(1)
salaDeLecturaVacia = Semaphore(1)

# Escritores
salaDeLecturaVacia.wait() # El escritor espera...
    # Usa el pizarrón en la sala de lectura
salaDeLecturaVacia.signal() # El escritor afirma...

# Lectores
mutex.wait()
    lectores += 1
    if lectores == 1:
        salaDeLecturaVacia.wait() # El primero en entrar espera...
mutex.signal()

    # Usan el pizarrón en la sala de lectura

mutex.wait()
    lectores -= 1
    if lectores == 0:
        salaDeLecturaVacia.signal() # El último en salir afirma... 
mutex.signal()
\end{verbatim}


\indent Un escritor espera a que la sala de lectura se encuentre vacía para poder entrar. 
Cuando sale, está seguro de que la sala está vacía y lo puede afirmar sin temor a 
equivocarse. 

\indent Los lectores van contando cuántos de ellos hay adentro de la sala. 
El primero en llegar tiene que esperar a que la sala de lectura esté vacía para poder entrar. 
Los siguientes en llegar pueden entrar a la sala sin esperar a que esté vacía, 
porque ya saben que hay al menos un lector adentro. Al mismo tiempo, el último en salir 
puede afirmar que la sala de lectura está vacía. 

\indent Notar que solo un lector puede estar esperando a que la sala de lectura se vacíe, 
mientras que muchos escritores pueden estar esperando eso mismo, y que si un 
lector afirma que la sala está vacía, está en lo cierto.

\indent Hay una parte del comportamiento de los lectores que responde 
a un patrón de semáforos conocido como \textbf{Lightswitch} o llave de luz: 
el primero en entrar prende la luz (o bloquea el semáforo) 
y el último en salir apaga la luz (o desbloquea el semáforo). 
Este patrón se puede encapsular en una clase de la siguiente manera:

\begin{verbatim}
Lightswitch:
    contador = 0
    mutex = Semaphore(1)
        
    lock(semaphore):
        mutex.wait()
        contador += 1
        if contador == 1:
            semaphore.wait()
        mutex.signal()

    unlock(semaphore):
        mutex.wait()
        contador -= 1
        if contador == 0:
            semaphore.signal()
        mutex.signal()
\end{verbatim}

\indent Ahora podemos reescribir la solución anterior al problema
de los lectores y escritores utilizando esta clase:

\begin{verbatim}
# Variables comunes
llaveDeLuzDeLectura = Lightswitch()
salaDeLecturaVacia = Semaphore(1)

# Escritores
salaDeLecturaVacia.wait() # El escritor espera...
    # Usa el pizarrón en la sala de lectura
salaDeLecturaVacia.signal() # El escritor afirma...

# Lectores
llaveDeLuzDeLectura.lock(salaDeLecturaVacia)
    # Usan el pizarrón en la sala de lectura
llaveDeLuzDeLectura.unlock(salaDeLecturaVacia)
\end{verbatim}

\indent ¿Este algoritmo está libre de inanición? 
Si un escritor llega cuando hay lectores en la sala de lectura, 
es posible que tenga que esperar por siempre, en tanto sigan llegando 
lectores antes de que la sala termine de vaciarse. Este algoritmo así planteado 
no se encuentra libre de inanición para los escritores.

\indent Para evitar esta situación es necesario agregar un semáforo más al que 
llamaremos \textbf{turnstile} o molinete, que funcionará como un molinete para 
los lectores, haciéndolos pasar de a uno por vez, y como un mutex para los 
escritores, excluyendo a todos los otros (lectores y escritores) de la sala de 
lectura. Entonces, el seudocódigo de la solución final al problema será:

\begin{verbatim}
# Variables comunes
llaveDeLuzDeLectura = Lightswitch()
salaDeLecturaVacia = Semaphore(1)
molinete = Semaphore(1)

# Escritores
molinete.wait()
    salaDeLecturaVacia.wait() # El escritor espera...
    # Usa el pizarrón en la sala de lectura
molinete.signal()

salaDeLecturaVacia.signal() # El escritor afirma...

# Lectores
molinete.wait()
molinete.signal()

llaveDeLuzDeLectura.lock(salaDeLecturaVacia)
    # Usan el pizarrón en la sala de lectura
llaveDeLuzDeLectura.unlock(salaDeLecturaVacia)
\end{verbatim}

\subsection{Implementación}

\indent Para no cometer errores necesitábamos que nuestra implementación fuera clara, fácil de leer y de entender. 
Para asegurarnos de que fuera correcta, tratamos que el paso del seudocódigo 
anterior a nuestro código sea casi directo. A la vez nos interesaba mantener la convención de Allen B. Downey 
en la que hacer $wait$ sobre una condición significa \textit{esperar a que dicha condición sea verdadera} y 
hacer $signal$ significa \textit{afirmar que es verdadera}. 

\indent Así pues, primero implementamos $wrappers$ para los $pthread\_mutex$ y para 
las variables de condición $pthread\_cond$ en las clases $Mutex$ y $Cond$ respectivamente. 
Todo el manejo de errores se realiza en este nivel de abstracción y se oculta en los 
niveles superiores. 

\indent Como nos interesaba conservar la semántica de $wait$ y $signal$, usamos una 
implementación propia de semáforos que se puede leer en la clase $Semaphore$. 
En este nivel de abstracción se tienen en cuenta las posibles $despertadas$ espúreas 
de las $pthread\_cond$. Si bien alcanzaba con la clase $Mutex$ para implementar el 
\textit{Read Write Lock}, implementar la clase $Semaphore$ nos ayudó a acortar el 
salto del seudocódigo al código. Además -¿por qué no decirlo?- queríamos aprovechar 
para ensayar una implementación de semáforos.

\indent También implementamos el patrón de semáforos \textbf{Lightswitch} en la clase 
$Lightswitch$.

\indent Usando estos elementos conseguimos que la distancia entre 
nuestra implementación del \textit{Read Write Lock} 
y el seudocódigo del algoritmo anterior sea 
muy pequeña, apenas una traducción. 
Vamos a copiar a continuación el contenido del archivo $RWLock.cpp$ (borrando los comentarios) 
sin ánimo de hacer $glosa$, sino tan solo 
para mostrar el parecido alcanzado. 
Lo mismo podría hacerse con el archivo $Lightswitch.cpp$. 
Con todo esto, esperamos que lo dicho antes acerca del seudocódigo 
valga para también para el código.

\newpage

\begin{verbatim}
RWLock::RWLock() {
    this->llave_de_luz_de_lectura = new Lightswitch();
    this->sala_de_lectura_vacia = new Semaphore(1);
    this->molinete = new Semaphore(1); 
}

void RWLock::rlock() {
    this->molinete->wait();
    this->molinete->signal();

    this->llave_de_luz_de_lectura->lock(sala_de_lectura_vacia);
}

void RWLock::runlock() {
    this->llave_de_luz_de_lectura->unlock(sala_de_lectura_vacia);
}

void RWLock::wlock() {
    this->molinete->wait();
        this->sala_de_lectura_vacia->wait();
}

void RWLock::wunlock() {
    this->molinete->signal();

    this->sala_de_lectura_vacia->signal(); 
}
\end{verbatim}


\subsection{Test de estrés}

\indent Diseñamos un test de estrés para poner a prueba nuestra implementación 
del \textit{Read Write Lock} capaz de lanzar lotes aleatorios de 131070 $threads$ 
escritores y lectores que operan sobre una única variable compartida que llamamos 
\textbf{pizarron}. Establecimos una 
probabilidad del 75\% de lanzar un $thread$ lector para que 1 de cada 4 $threads$ 
fuera un escritor. Para poder lanzar tantos $threads$ tuvimos que usar la instrucción 
$pthread\_detach$ para soltar a cada $thread$ después de crearlo. Todo esto se puede 
leer en el archivo $Estres.cpp$.

\indent Los lectores piden un \textbf{read lock}, ejecutan un lote de instrucciones espúreas, 
leen la variable compartida, guardan el valor leído en una variable auxiliar 
y, a continuación, realizan 20000 nuevas lecturas de la variable compartida 
comparando el nuevo valor leído con el valor guardado.

\indent Los escritores piden un \textbf{write lock}, ejecutan un lote de instrucciones espúreas, 
incrementan en 1 la variable compartida, guardan el resultado en una variable auxiliar 
y, a continuación, realizan 20000 nuevas lecturas de la variable compartida 
comparando el nuevo valor leído con el valor guardado.

\indent Si algún escritor entra a la sala de lectura y escribe en el pizarrón mientras otros $threads$ 
(lectores o escritores) se encuentran dentro de la sala, fallará alguna comparación y se registrará el fallo.

\indent Después modificamos levemente a los escritores para que realicen 20000 escrituras de la 
variable compartida en vez de 20000 lecturas. 
Ahora, si algún lector entra en la sala de lectura mientras un escritor se encuentra adentro, 
fallará alguna comparación realizada por el lector y se registrará el fallo.

\indent Para obtener el resultado de los fallos registrados por cada $thread$ usamos un 
arreglo de punteros a entero y le pasamos cada uno de estos punteros como parámetro a cada 
$thread$. A final de cada lote de 131070 $threads$ revisamos el arreglo y contamos los fallos.

\indent Nos fue necesario ajustar la cantidad de operaciones espúreas para incrementar la concurrencia y 
alcanzamos picos de más 500 $threads$ ejecutando al mismo tiempo. 

\indent Tuvimos la oportunidad de correr 100 lotes de 131070 $threads$ 
(con una semilla distinta cada vez) en una computadora con 2 núcleos 
y en una computadora con 4 núcleos sin detectar ningún fallo.

\indent Sin embargo, a pesar de ejecutar tantas pruebas, aún nos faltaba verificar que nuestra 
implementación del \textit{Read Write Lock} estuviera libre de inanición para los escritores. 
Modificamos una vez más a los lectores y a los escritores para que imprimieran por $sterr$ 
el valor de la variable compartida y así poder observar la secuencia. A continuación copiamos 
un fragmento de la salida:

\begin{verbatim}
E: 3394
L: L: L: 3394L: 3394L: L: 
3394
33943394


3394
E: 3395
E: 3396
L: L: 3396
L: 3396
3396
L: 3396
L: 3396
E: 3397
L: 3397
E: 3398
L: 3398
L: 3398
L: L: L: 339833983398
\end{verbatim}

\indent Podemos observar la alternancia entre escritores y lectores e incluso la concurrencia 
de lectores.
\indent Nos animamos a afirmar, por el momento, que nuestra implementación del \textit{Read Write Lock} es 
correcta y está libre de inanición.


